package week_10.实验3_查找和排序.cn.edu.besti.cs1723.LXY2328;

import week_7.jsjf.LinkedBinarySearchTree;


public class Searching {
    //线性查找
    public static<T> boolean linearSearch(T[] data, int min, int max, T target)
    {
        int index = min;
        boolean found = false;

        while (!found && index <= max)
        {
            found = data[index].equals(target);
            index++;
        }

        return found;
    }
    //顺序查找
    public static <T extends Comparable<T>> boolean SequenceSearch(T[] data, int min, int max, T target) {
        int index = min;
        boolean found = false;
        while (!found && index <= max) {
            found = data[index].equals(target);
            index++;
        }
        return found;
    }
    //二分查找
    public static int binarySearch(int[] array, int searchKey) {

        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = (low + high) / 2;
            if (searchKey == array[middle]) {
                return middle;
            } else if (searchKey < array[middle]) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }
     //插值查找
    public static int InsertionSearch(int[] a, int value, int low, int high) {
        int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low);
        if (a[mid] == value)
            return mid;
        if (a[mid] > value)
            return InsertionSearch(a, value, low, mid - 1);
        else
            return InsertionSearch(a, value, mid + 1, high);
    }
    //斐波那契查找算法
    public static boolean fibonacciSearch(int[] table, int keyWord) {
        //确定需要的斐波那契数
        int i = 0;
        while (getFibonacci(i) - 1 == table.length) {
            i++;
        }
        //开始查找
        int low = 0;
        int height = table.length - 1;
        while (low <= height) {
            int mid = low + getFibonacci(i - 1);
            if (table[mid] == keyWord) {
                return true;
            } else if (table[mid] > keyWord) {
                height = mid - 1;
                i--;
            } else if (table[mid] < keyWord) {
                low = mid + 1;
                i -= 2;
            }
        }
        return false;
    }

    //得到第n个斐波那契数
    public static int getFibonacci(int n) {
        int res = 0;
        if (n == 0) {
            res = 0;
        } else if (n == 1) {
            res = 1;
        } else {
            int first = 0;
            int second = 1;
            for (int i = 2; i <= n; i++) {
                res = first + second;
                first = second;
                second = res;
            }
        }
        return res;
    }
    //树表查找
    public static <T extends Comparable<? super T>>
    boolean binaryTreeSearch(T[] data, int min, int max, T target)
    {
        boolean found = false;
        LinkedBinarySearchTree linkedBinarySearchTree = new LinkedBinarySearchTree();
        // Comparable<T> comparableElement = (Comparable<T>)target;
        for (int i=min;i<=max;i++)
            linkedBinarySearchTree.addElement(data[i]);

        while (found==false&&linkedBinarySearchTree.root!=null) {
            if (target.equals(linkedBinarySearchTree.root.getElement())){
                found = true;
            }
            else
            {
                if (target.compareTo((T)linkedBinarySearchTree.root.getElement()) < 0)
                    linkedBinarySearchTree.root = linkedBinarySearchTree.root.left;
                else
                    linkedBinarySearchTree.root = linkedBinarySearchTree.root.getRight();
            }
        }
        return found;
    }
    //分块查找
    public static <T extends Comparable<? super T>> boolean BlockSearch(T[] data, int min, int max,T target) {
        boolean found = false;
        int area = block(data,min,max);
        int leftarea = block(data,min,area-1);
        int rightarea = block(data,area+1,max);

        if (target.compareTo(data[area]) == 0)
            found = true;
        else
        {
            if (target.compareTo(data[area]) < 0)
            {
                if (target.compareTo(data[leftarea]) == 0)
                    found = true;
                else
                {
                    if (target.compareTo(data[leftarea]) < 0)
                        found =  linearSearch(data,min,leftarea-1,target);
                    else
                        found =  linearSearch(data,leftarea+1,area-1,target);
                }
            }
            else
            {
                if (target.compareTo(data[rightarea]) == 0)
                    return true;
                else
                {
                    if (target.compareTo(data[rightarea]) < 0)
                        found = linearSearch(data,area+1,rightarea-1,target);
                    else
                        found = linearSearch(data,rightarea+1,max,target);
                }
            }
        }
        return found;
    }

    private static <T extends Comparable<? super T>> int block(T[] data, int min, int max)
    {
        T partitionelement;
        int left, right;
        int middle = (min + max) / 2;


        partitionelement = data[middle];

        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right)
        {
            while (left < right && data[left].compareTo(partitionelement) <= 0)
                left++;
            while (data[right].compareTo(partitionelement) > 0)
                right--;
            if (left < right)
                swap(data, left, right);
        }

        swap(data, min, right);

        return right;
    }

    private static <T extends Comparable<? super T>> void swap(T[] data, int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }


    //哈希算法
    public static <T extends Comparable<? super T>>
    boolean HashSearch(int[] data, int min, int max, int target)
    {
        boolean result = false;
        Hash hashConflict = new Hash();
        for (int i=0;i<data.length;i++)
            hashConflict.ReceiveNum(data[i]);
        int index = target%hashConflict.num;
        while (hashConflict.list[index]!=null&&result==false)
        {
            if (hashConflict.list[index].getElement().equals(target))
                result = true;
            else
                hashConflict.list[index] = hashConflict.list[index].getNext();
        }
        return result;
    }

}
